package com.adee.zingfront;

import java.util.ArrayList;
import java.util.List;

/**
 * 夏季割麦子，需要用到大型收割机，现在有 n 块麦地需要收割，每个麦地的收割时间都不同，第 n 个麦田的开始时
 * 间是 start_n， 第 n 个麦田的结束时间是 end_n，下面是各个麦田收割的开始以及结束时间数组： [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9)]，其中(1,4)代表第一个麦田，1 点开始，4 点结束，其他以此类推；
 * 请通过编程计算出最少需要多少辆收割机能收完？ps：一个收割机在一个麦田上面继续收割时，必须连续工作直至当
 * 前麦田收割完成；
 *
 * 思路：问题转化：在全部n个区间中，存在m个区间，满足这m个区间存在公共区间，求m的最大值。
 * arr = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9)]
 * 解法：将每个区间的起点和终点统一从小到大排序，然后遍历有序数组，遇到起点加1，遇到终点减1，并且每次遍历一点时，记录最大值。
 */
public class Test2 {
    public static void main(String[] args) {
        int[][] arr = new int[][]{{1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 9}};
        List<Dot> list = new ArrayList<>();
        for(int i = 0; i < arr.length; i++) {
            int[] section = arr[i];
            list.add(new Dot(section[0], true));
            list.add(new Dot(section[1], false));
        }
        list.sort((a,b) -> a.value-b.value);
        int max = 1; // 最大重叠区间数
        int count = 0; // 计数器，遇到起点+1，遇到终点-1
        for (Dot d : list) {
            if (d.isBegin) {
                count++;
                max = Math.max(max, count);
            } else {
                count--;
            }
        }
        System.out.println(String.format("至少需要%d辆收割机", max)); // 输出结果
    }

    static class Dot{
        int value; // 区间点坐标值
        boolean isBegin; // 是否为区间起点，true起点，false终点
        public Dot(int value, boolean isBegin) {
            this.value = value;
            this.isBegin = isBegin;
        }
    }
}
